package monotonestack;

import java.util.Arrays;
import java.util.LinkedList;
import java.util.Stack;

class Solution739 {
    public static void main(String[] args) {
        Solution739 solution739 = new Solution739();
//        System.out.println(Arrays.toString(solution739.dailyTemperatures(new int[]{73,74,75,71,69,72,76,73})));
        System.out.println(Arrays.toString(solution739.dailyTemperatures(new int[]{73,43,100})));
        System.out.println(Arrays.toString(solution739.dailyTemperatures(new int[]{73,43,32,40})));
    }
    public int[] dailyTemperatures(int[] temperatures) {

        int n = temperatures.length;
        int[] answer = new int[n];
        // 尚未找到下一个更高温度的索引
        Stack<Integer> stack = new Stack<>();

        for (int i = 0; i < n; i++) {
            while (!stack.isEmpty() && temperatures[i] > temperatures[stack.peek()]) {
                int prevIndex = stack.pop();
                answer[prevIndex] = i - prevIndex;
            }
            stack.push(i);
        }

        return answer;
    }
}